1417. Queen Move

There is a queen on the chessboard of size m × n. How many squares does the queen attack?

Input. Four positive integers: the size of the chessboard m and n and the queen's coordinates x and y (1 ≤ x ≤ m ≤ 10⁹, 1 ≤ y ≤ n ≤ 10⁹).

Output. Print the number of squares the queen attacks.

Sample input	Sample output
8 8 4 5	27

SOLUTION

mathematics

Algorithm analysis

The line with the queen contains n squares. Hence, the number of squares where the queen can move horizontally equals to n – 1. The column with the queen contains m squares. Hence, the number of squares where the queen can move vertically equals m – 1. So the queen attacks n – 1 + m – 1 squares horizontally and vertically.

Divide the board into 4 parts with horizontal and vertical lines passing through the square with the queen. In each part, count the number of squares under attack.

Consider, for example, the upper right quarter. It has length n – y squares and width x – 1 squares. There are min(x – 1, n – y) squares under the queen’s attack. Similarly, for:

· upper left quarter, the queen attacks min(x – 1, y – 1) squares;

· bottom left quarter, the queen attacks min(m – x, y – 1) squares;

· bottom right quarter, the queen attacks min(m – x, n – y) squares;

Example

Consider an example where the board size is 8 × 8 and the queen is in position (4, 5).

There are n – 1 + m – 1 = 7 + 7 = 14 squares under the horizontal and vertical attack of the queen. Let’s look at four quarters. Under the attack of the queen will be:

· in the upper left quarter min(4, 3) = 3 squares;

· in the lower left quarter min(4, 4) = 4 squares;

· in the lower right quarter min(3, 4) = 3 squares;

· in the upper right quarter min(3, 3) = 3 squares;

In total, there are 14 + 3 + 4 + 3 + 3 = 27 squares under the queen’s attack.

Algorithm realization

Read the input data.

scanf("%d %d %d %d", &m, &n, &x, &y);

Assign to the variable s the number of squares that the queen attacks with horizontal or vertical moves.

s = m - 1 + n - 1; // horiz & vertical

Add the diagonal squares that are under attack.

s += min(m - x, n - y); // (x,y) -> (m, n)

s += min(m - x, y - 1); // (x,y) -> (m, 1)

s += min(x - 1, n - y); // (x,y) -> (1, n)

s += min(x - 1, y - 1); // (x,y) -> (1, 1)

Print the answer.

printf("%lld\n", s);